import re


class Solution:
    """这题确实有点自闭,找不到好的方法,完全就是最暴力的枚举法在做,其实少写了些情况,感觉这样下去没意义"""
    def removeInvalidParentheses(self, s: str) -> list:
        # 先删除最边上不对的括号
        while True:
            mid = s
            s = re.sub(r"^([^()]*)\)*", r"\1", s)
            s = re.sub(r"^(\(\))\)*", r"\1", s)
            s = re.sub(r"\(*([^()]*)$", r"\1", s)
            s = re.sub(r"\(*(\(\))$", r"\1", s)
            if mid == s:
                break
        # 先拒绝一些情况,没有一对有效括号的,还有本来就是有效的
        if not re.search(r"\([^()]*?\)", s):
            return [re.sub(r"[()]", "", s)]
        mid_2 = s
        while re.search(r"\([^()]*?\)", mid_2):
            mid_2 = re.sub(r"\([^()]*?\)", "", mid_2)
        if not mid_2 or ("(" not in mid_2 and ")" not in mid_2):
            return [s]
        # print(s)
        res = []
        count_left, count_right = s.count("("), s.count(")")
        mid_list = []
        if count_left != count_right:
            # 如果括号数量不相等,先想办法删到括号相等
            if count_left > count_right:
                mid_s = "("
            else:
                mid_s = ")"
            delete_num, i = abs(count_left - count_right), 0
            kuohao_num_list = []
            try:
                while True:
                    kuohao_num_list.append(s.index(mid_s, i))
                    i = kuohao_num_list[-1] + 1
            except:
                pass
            kuohao_num_list.reverse()
            delete_list = [[]]
            for i in range(delete_num):
                delete_list = [lists + [j] for lists in delete_list for j in kuohao_num_list if j not in lists]
            for lists in delete_list:
                mid_res = s
                for num in lists:
                    mid_res = mid_res[:num] + mid_res[num+1:]
                mid_2 = mid_res
                while re.search(r"\([^()]*?\)", mid_2):
                    mid_2 = re.sub(r"\([^()]*?\)", "", mid_2)
                if (not mid_2 or ("(" not in mid_2 and ")" not in mid_2)) and mid_res not in res:
                    res.append(mid_res)
            if res:
                return res
            else:
                # TODO:应该有还需要删除整对括号的情况
                pass
        # 如果上面的得不出结果,或者直接括号数量就相等
        else:
            left_kuohao_num_list = []
            right_kuohao_num_list = []
            i = 0
            try:
                while True:
                    left_kuohao_num_list.append(s.index("(", i))
                    i = left_kuohao_num_list[-1] + 1
            except:
                pass
            i = 0
            try:
                while True:
                    right_kuohao_num_list.append(s.index(")", i))
                    i = right_kuohao_num_list[-1] + 1
            except:
                pass
            delete_list = [[i, j] for i in left_kuohao_num_list for j in right_kuohao_num_list]
            for lists in delete_list:
                mid_res = s
                for num in lists:
                    mid_res = mid_res[:num] + mid_res[num+1:]
                mid_2 = mid_res
                while re.search(r"\([^()]*?\)", mid_2):
                    mid_2 = re.sub(r"\([^()]*?\)", "", mid_2)
                if not mid_2:
                    if mid_res not in res:
                        res.append(mid_res)
                else:
                    if mid_res not in mid_list:
                        mid_list.append(mid_res)
            if res:
                return res
            else:
                # TODO:应该有删除一对不够的情况
                pass


a = Solution()
print(a.removeInvalidParentheses("()())()"))
print(a.removeInvalidParentheses("(a)())()"))
print(a.removeInvalidParentheses(")("))
print(a.removeInvalidParentheses(")a("))
print(a.removeInvalidParentheses(")()("))
print(a.removeInvalidParentheses("p(r)"))
print(a.removeInvalidParentheses("))(()("))
print(a.removeInvalidParentheses("())(((()m)("))
